<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function Node(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var a = new Node(1)
        var b = new Node(null)
        var c = new Node(2)
        var d = new Node(3)
        var e = new Node(4)
        var f = new Node(5)
        var g = new Node(6)
        a.left = b
        a.right = c
        b.left = d
        b.right = e
        c.left = f
        c.right = g

        /* 
        1 思路：中左右遍历+碰到叶子结点+拼接字符串+回溯
        2 时间复杂度：O(n)
          空间复杂度: O(n) 结果数组 + 路径数组
        
        */
        var binaryTreePaths = function (root) {
            debugger
            // 结果数组
            let res = []
            // 路径数组
            let path = []
            // 判空
            if (root === null) {
                return res
            }
            // 递归调用
            traversal(root, path, res)
            return res
        }

        function traversal(cur, path, res) {
            debugger
            path.push(cur.val)

            // 叶子节点
            if (cur.left === null && cur.right === null) {
                let sPath = ''
                for (let i = 0; i < path.length - 1; i++) {
                    sPath += String(path[i])
                    sPath += '->'
                }

                sPath += String(path[path.length - 1])
                res.push(sPath)
                return
            }

            if (cur.left) {
                traversal(cur.left, path, res)
                // 回溯的体现
                path.pop()
            }
            if (cur.right) {
                traversal(cur.right, path, res)
                // 回溯的体现
                path.pop()
            }
        }
        console.log(binaryTreePaths(a));
    </script>
</body>

</html>